#include <stdlib.h>
#include <list>
#include <ut/UnitTest.h>
#include <illib/Log.h>
#include <illib/Allocator.h>
#include <illib/System.h>
#include <illib/Exception.h>

using namespace illib;
using namespace std;

namespace illib_ut{
	void Allocator_ut(){
		ut::UnitTestLogger logger(TN(ut::illib::Allocatorut));
		{
			ut::test(AT(), EX(MemoryTracker::tracker().empty()), TN(MemoryTracker::Tracker));
			int a;
			void * b = malloc(10);
			ut::test(AT(), EX(MemoryTracker::tracker().stack(&a)), TN(illib::MemoryTracker::Tracker::stack));
			ut::test(AT(), EX(!MemoryTracker::tracker().stack(b)), TN(illib::MemoryTracker::Tracker::stack));
			free(b);
		}
		for(uint8_t n = 0; n < 5; n++)
		{
			uint8_t alignment = 1 << n;
			size_t calculatedBlockSize = 0;
			size_t calculatedItemCount = 0;
			size_t calculatedMapSize = 0;
			try{
				calculatedBlockSize = PoolAllocator::Pool::calculateMemorySize(0, 10, alignment);
				ut::test(AT(), EX(false), TN(PoolAllocator::Pool::calculateMemoryBlockSize));
			} catch(Exception &e){
				ut::test(AT(), EX(true), TN(Pool::calculateMemoryBlockSize));
			}

			try{
				calculatedBlockSize = PoolAllocator::Pool::calculateMemorySize(10, 0, alignment);
				ut::test(AT(), EX(false), TN(PoolAllocator::Pool::calculateMemoryBlockSize));
			} catch(Exception &e){
				ut::test(AT(), EX(true), TN(PoolAllocator::Pool::calculateMemoryBlockSize));
			}

			try{
				calculatedItemCount = PoolAllocator::Pool::calculateItemCount(0, 10, alignment);
				ut::test(AT(), EX(false), TN(PoolAllocator::Pool::calculateItemCount));
			} catch(Exception &e){
				ut::test(AT(), EX(true), TN(PoolAllocator::Pool::calculateItemCount));
			}

			try{
				calculatedItemCount = PoolAllocator::Pool::calculateItemCount(10, 0, alignment);
				ut::test(AT(), EX(false), TN(PoolAllocator::Pool::calculateItemCount));
			} catch(Exception &e){
				ut::test(AT(), EX(true), TN(PoolAllocator::Pool::calculateItemCount));
			}

			try{
				calculatedItemCount = PoolAllocator::Pool::calculateItemCount(10, 10, alignment);
				ut::test(AT(), EX(false), TN(PoolAllocator::Pool::calculateItemCount));
			} catch(Exception &e){
				ut::test(AT(), EX(true), TN(PoolAllocator::Pool::calculateItemCount));
			}

			try{
				calculatedItemCount = PoolAllocator::Pool::calculateItemCount(20, 10, alignment);
				ut::test(AT(), EX(true), TN(PoolAllocator::Pool::calculateItemCount));
			} catch(Exception &e){
				ut::test(AT(), EX(false), TN(PoolAllocator::Pool::calculateItemCount));
			}

			for(n = 0; n < 5; n++){
				uint8_t alignment = 0x1 << n;
				for(size_t itemCount = 1; itemCount < 100; itemCount++){
					for(size_t itemSize = 1; itemSize < 100; itemSize++){
						calculatedBlockSize = PoolAllocator::Pool::calculateMemorySize(itemSize, itemCount, alignment);
						calculatedItemCount = PoolAllocator::Pool::calculateItemCount(calculatedBlockSize, itemSize, alignment);
						calculatedMapSize = PoolAllocator::Pool::calculateMapSize(calculatedBlockSize, itemSize, alignment);
						//if (itemCount != calculatedItemCount) Console::print("%d %d\n", itemCount, calculatedItemCount);
						ut::test(AT(), EX(itemCount == calculatedItemCount), TN(PoolAllocator::Pool::calculateItemCount));
						assert(itemCount == calculatedItemCount);
						size_t mapSize;
						if(itemCount % 8 == 0) mapSize = ((itemCount) >> 3);
						else mapSize = ((itemCount) >> 3) + 1;
						uint8_t padding = mapSize % alignment;
						if (padding) padding = alignment-padding;
						ut::test(AT(), EX(calculatedMapSize == mapSize + padding), TN(PoolAllocator::Pool::calculateMapSize));
					}
				}
			}
		}
		ut::test(AT(), EX(MemoryTracker::tracker().empty()), TN(MemoryTracker::Tracker));
		{
			uint8_t memory[113];
			list<uint8_t*> pointers;
			size_t size = sizeof(uint8_t);
			PoolAllocator::Pool pool(memory,sizeof(memory),size, 1, 0);
			size_t count = pool.capacity();

			size_t allocatedSize;
			ut::test(AT(), EX(!pool.release(0)), TN(Pool::free));
			ut::test(AT(), EX(pool.empty()), TN(Pool::empty));
			for(size_t i = 0; i < count; i++){
				uint8_t *pointer;

				ut::test(AT(), EX((pointer = pool.allocate(size, allocatedSize)) != 0), TN(Pool::allocate));
				pointers.push_back(pointer);
			}
			ut::test(AT(), EX(pool.full()), TN(Pool::full));
			ut::test(AT(), EX(pool.allocate(size, allocatedSize) == 0), TN(Pool::allocate));
			for(size_t i = 0; i< 1000; i++){
				if(pool.empty()){
					for(size_t j = 0; j < count; j++){
						uint8_t *pointer;
						ut::test(AT(), EX((pointer = pool.allocate(size, allocatedSize)) != 0), TN(Pool::allocate));
						pointers.push_back(pointer);
					}
				}
				if((rand() % 2 == 0) && !pool.full()){
					uint8_t *pointer;
					ut::test(AT(), EX((pointer = pool.allocate(size, allocatedSize)) != 0), TN(Pool::allocate));
					pointers.push_back(pointer);
				} else {
					for(size_t j = 0; j < 5; j++){
						if(pointers.size() == 0) break;
						size_t index = rand()%pointers.size();
						list<uint8_t*>::iterator iter = pointers.begin();
						for(size_t k = 0; k < index; k++) iter++;
						ut::test(AT(), EX(pool.release(*iter)), TN(PoolAllocator::Pool::release));
						pointers.erase(iter);
					}
				}
			}
			pool.clear();
		}
		ut::test(AT(), EX(MemoryTracker::tracker().empty()), TN(MemoryTracker::Tracker));
		{
			MemoryTracker::MemoryTree tree;
			MemoryTracker::MemoryTreeFunctions functions;
			MemoryTracker::DummyTracked m1(reinterpret_cast<uint8_t * >(40),10);
			MemoryTracker::DummyTracked m2(reinterpret_cast<uint8_t * >(60),10);
			MemoryTracker::DummyTracked m3(reinterpret_cast<uint8_t * >(80),10);
			tree.add(m1, functions);
			tree.add(m2, functions);
			tree.add(m3, functions);

			MemoryTracker::DummyTracked f1(reinterpret_cast<uint8_t * >(50),0);
			BasicRedBlackTree::Iterator i1(f1, tree, functions);
			ut::test(AT(), EX(i1.current() != 0), TN(BasicRedBlackTree::Iterator::current));

			MemoryTracker::DummyTracked f2(reinterpret_cast<uint8_t * >(10),0);
			BasicRedBlackTree::Iterator i2(f2, tree, functions);
			ut::test(AT(), EX(i2.current() == 0), TN(BasicRedBlackTree::Iterator::current));
		}
		ut::test(AT(), EX(MemoryTracker::tracker().empty()), TN(MemoryTracker::Tracker));
		{
			PoolAllocator::BasicAllocator allocator(100, System::allocator().pagesize(), 1, 0);
		}
		ut::test(AT(), EX(MemoryTracker::tracker().empty()), TN(MemoryTracker::Tracker));
		{
			size_t size = 100;
			PoolAllocator::BasicAllocator allocator(size, System::allocator().pagesize(), 1, 0);
			size_t allocatedSize;
			MemoryTracker::Tracked * entry;
			void * ptr = 0;

			ptr = allocator.allocate(size, allocatedSize);
			ut::test(AT(), EX(ptr!= 0), TN(PoolAllocator::BasicAllocator::allocate));
			entry = MemoryTracker::tracker().entry(ptr);
			ut::test(AT(), EX(entry != 0), TN(MemoryTracker::Tracker::entry));
			ut::test(AT(), EX(entry->allocator()), TN(Tracked::allocator));
			ut::test(AT(), EX(entry->allocator()->root() == &allocator), TN(Tracked::root));
			ut::test(AT(), EX(entry->allocator()->release(ptr)), TN(PoolAllocator::BasicAllocator::release));
		}
		ut::test(AT(), EX(MemoryTracker::tracker().empty()), TN(MemoryTracker::Tracker));
		{
			size_t size = 10;
			PoolAllocator::BasicAllocator poolAllocator(size, System::allocator().pagesize(), 1, 0);
			size_t allocatedSize;
			for(size_t i = 0; i < 2*(System::allocator().pagesize()/size); i++){
				ut::test(AT(), EX(poolAllocator.allocate(size, allocatedSize) != 0), TN(PoolAllocator::BasicAllocator::allocate));
			}
			poolAllocator.clear();
		}
		ut::test(AT(), EX(MemoryTracker::tracker().empty()), TN(MemoryTracker::Tracker));
		{
			BlockAllocator::BasicAllocator allocator(1, 0);
		}
		{
			ut::test(AT(), EX(MemoryTracker::tracker().empty()), TN(MemoryTracker::Tracker));
		}
		ut::test(AT(), EX(MemoryTracker::tracker().empty()), TN(MemoryTracker::Tracker));
		{
			BlockAllocator::BasicAllocator allocator(1, 0);
			size_t size;
			MemoryTracker::Tracked * entry;
			void * ptr = 0;

			ptr = allocator.allocate(10, size);
			ut::test(AT(), EX(ptr!= 0), TN(BlockAllocator::BasicAllocator::allocate));
			entry = MemoryTracker::tracker().entry(ptr);
			ut::test(AT(), EX(entry != 0), TN(MemoryTracker::Tracker::entry));
			ut::test(AT(), EX(entry->allocator()), TN(Tracked::allocator));
			ut::test(AT(), EX(entry->allocator()->root() == &allocator), TN(Tracked::root));
			ut::test(AT(), EX(entry->allocator()->release(ptr)), TN(PoolAllocator::BasicAllocator::allocate));

			ptr = allocator.allocate(100, size);
			ut::test(AT(), EX(ptr!= 0), TN(BlockAllocator::BasicAllocator::allocate));
			entry = MemoryTracker::tracker().entry(ptr);
			ut::test(AT(), EX(entry != 0), TN(MemoryTracker::Tracker::entry));
			ut::test(AT(), EX(entry->allocator()), TN(Tracked::allocator));
			ut::test(AT(), EX(entry->allocator()->root() == &allocator), TN(Tracked::root));
			ut::test(AT(), EX(entry->allocator()->release(ptr)), TN(PoolAllocator::BasicAllocator::allocate));

			ptr = allocator.allocate(1000, size);
			ut::test(AT(), EX(ptr!= 0), TN(BlockAllocator::BasicAllocator::allocate));
			entry = MemoryTracker::tracker().entry(ptr);
			ut::test(AT(), EX(entry != 0), TN(MemoryTracker::Tracker::entry));
			ut::test(AT(), EX(entry->allocator()), TN(Tracked::allocator));
			ut::test(AT(), EX(entry->allocator()->root() == &allocator), TN(Tracked::root));
			ut::test(AT(), EX(entry->allocator()->release(ptr)), TN(PoolAllocator::BasicAllocator::allocate));

			ptr = allocator.allocate(10000, size);
			ut::test(AT(), EX(ptr!= 0), TN(BlockAllocator::BasicAllocator::allocate));
			entry = MemoryTracker::tracker().entry(ptr);
			ut::test(AT(), EX(entry != 0), TN(MemoryTracker::Tracker::entry));
			ut::test(AT(), EX(entry->allocator()), TN(Tracked::allocator));
			ut::test(AT(), EX(entry->allocator()->root() == &allocator), TN(Tracked::root));
			ut::test(AT(), EX(entry->allocator()->release(ptr)), TN(PoolAllocator::BasicAllocator::allocate));

			ptr = allocator.allocate(100000, size);
			ut::test(AT(), EX(ptr!= 0), TN(BlockAllocator::BasicAllocator::allocate));
			entry = MemoryTracker::tracker().entry(ptr);
			ut::test(AT(), EX(entry != 0), TN(MemoryTracker::Tracker::entry));
			ut::test(AT(), EX(entry->allocator()), TN(Tracked::allocator));
			ut::test(AT(), EX(entry->allocator()->root() == &allocator), TN(Tracked::root));
			ut::test(AT(), EX(entry->allocator()->release(ptr)), TN(PoolAllocator::BasicAllocator::allocate));

			ptr = allocator.allocate(100000, size);
			ut::test(AT(), EX(ptr!= 0), TN(BlockAllocator::BasicAllocator::allocate));
			entry = MemoryTracker::tracker().entry(ptr);
			ut::test(AT(), EX(entry != 0), TN(MemoryTracker::Tracker::entry));
			ut::test(AT(), EX(entry->allocator()), TN(Tracked::allocator));
			ut::test(AT(), EX(entry->allocator()->root() == &allocator), TN(Tracked::root));
			ut::test(AT(), EX(entry->allocator()->release(ptr)), TN(PoolAllocator::BasicAllocator::allocate));

			ptr = allocator.allocate(1000000, size);
			ut::test(AT(), EX(ptr!= 0), TN(BlockAllocator::BasicAllocator::allocate));
			entry = MemoryTracker::tracker().entry(ptr);
			ut::test(AT(), EX(entry != 0), TN(MemoryTracker::Tracker::entry));
			ut::test(AT(), EX(entry->allocator()), TN(Tracked::allocator));
			ut::test(AT(), EX(entry->allocator()->root() == &allocator), TN(Tracked::root));
			ut::test(AT(), EX(entry->allocator()->release(ptr)), TN(PoolAllocator::BasicAllocator::allocate));
		}
		ut::test(AT(), EX(MemoryTracker::tracker().empty()), TN(MemoryTracker::Tracker));
	}
};
